#include <iostream>
#include <vector>

using namespace std;
class Solution
{

public:
   int islandPerimeter(vector<vector<int>> &grid)
   {
      constexpr static int dx[4] = {0, 1, 0, -1};
      constexpr static int dy[4] = {1, 0, -1, 0};
      int n = grid.size(), m = grid[0].size();
      int ans = 0;
      for (int i = 0; i < n; ++i)
      {
         for (int j = 0; j < m; ++j)
         {
            if (grid[i][j])
            {
               int cnt = 0;
               for (int k = 0; k < 4; ++k)
               {
                  int tx = i + dx[k];
                  int ty = j + dy[k];
                  if (tx < 0 || tx >= n || ty < 0 || ty >= m || !grid[tx][ty])
                  {
                     cnt += 1;
                  }
               }
               ans += cnt;
            }
         }
      }
      return ans;
   }

   int dfs(int x, int y, vector<vector<int>> &grid, int n, int m)
   {
      constexpr static int dx[4] = {0, 1, 0, -1};
      constexpr static int dy[4] = {1, 0, -1, 0};
      if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0)
      {
         return 1;
      }
      if (grid[x][y] == 2)
      {
         return 0;
      }
      grid[x][y] = 2;
      int res = 0;
      for (int i = 0; i < 4; ++i)
      {
         int tx = x + dx[i];
         int ty = y + dy[i];
         res += dfs(tx, ty, grid, n, m);
      }
      return res;
   }
   int islandPerimeter_2(vector<vector<int>> &grid)
   {
      int n = grid.size(), m = grid[0].size();
      int ans = 0;
      for (int i = 0; i < n; ++i)
      {
         for (int j = 0; j < m; ++j)
         {
            if (grid[i][j] == 1)
            {
               ans += dfs(i, j, grid, n, m);
            }
         }
      }
      return ans;
   }

   int islandPerimeter_3(vector<vector<int>> &grid)
   {
      int num = 0;
      for (int i = 0; i < grid.size(); i++)
      {
         for (int j = 0; j < grid[i].size(); j++)
         {
            if (grid[i][j] == 1)
            {
               num += 4;
               if (i + 1 < grid.size() && grid[i + 1][j] == 1)
               {
                  num -= 2;
               }
               if (j + 1 < grid[i].size() && grid[i][j + 1] == 1)
               {
                  num -= 2;
               }
            }
         }
      }
      return num;
   }

   int islandPerimeter_4(vector<vector<int>> &grid)
   {
      int row = grid.size(), column = grid[0].size();
      int res = 0;
      for (int i = 0; i < row; i++)
      {
         for (int j = 0; j < column; j++)
         {
            if (grid[i][j])
            {
               if (j == 0 || grid[i][j - 1] == 0)
               {
                  res++;
               }
               if (j == column - 1 || grid[i][j + 1] == 0)
               {
                  res++;
               }
               if (i == 0 || grid[i - 1][j] == 0)
               {
                  res++;
               }
               if (i == row - 1 || grid[i + 1][j] == 0)
               {
                  res++;
               }
            }
         }
      }
      return res;
   }
};
int main()
{
   Solution s;
   vector<vector<int>> grid = {{0, 1, 0, 0}, {1, 1, 1, 0}, {0, 1, 0, 0}, {1, 1, 0, 0}};
   cout << s.islandPerimeter_3(grid) << endl;
   system("pause");
   return 0;
}
